Compilers are programs that compile a source program (such as source code or byte code) into a target program for a target computing device so that the target computing device is able to understand and execute the target program. FIG. 1 illustrates front end and back end phases of a typical compiler. As illustrated, typical front end phases include lexical analysis, syntax analysis, semantic analysis, and intermediate code generation. Also as illustrated, back end phases typically include optional machine-independent code optimization performed on an intermediate representation, target computing device code generation, and optional machine-dependent code optimization performed on the target computing device specific code. FIG. 2 illustrates subphases performed in typical back end code generation. As illustrated, typical subphases include instruction selection, data-flow analysis, optional global and/or local early instruction scheduling (instruction scheduling performed before register allocation), register allocation, late instruction scheduling (instruction scheduling performed after register allocation), and object file creation.
Typically, intermediate representations store data in virtual registers. During register allocation, these virtual registers are mapped to the physical registers of the target computing device that will actually store the data represented by the virtual registers while the target computing device executes the code. However, the number of live virtual registers is not constrained to the number of physical registers that a target computing device actually includes. Data-flow analysis is used to compute the liveness of the virtual registers at each program point. The register pressure at a program point is just the number of live virtual registers. The register pressure is excessive when the number of live virtual registers exceeds the number of physical registers on the target computing device. In addition to mapping virtual registers to physical registers, register allocation typically spills virtual registers (stores virtual registers in memory and reloads them from memory when needed) when register pressure is excessive such that all virtual registers are either stored in memory or physical registers.
Because excessive register pressure is typically not handled until register allocation, early instruction schedulers generally have to consider and attempt to minimize register pressure. This reduces the effectiveness of early instruction schedulers to focus on minimizing stalls in execution. Further, because instructions for spilling the virtual registers are not typically inserted until register allocation, early instruction schedulers cannot optimize those later inserted instructions. Late instruction scheduling typically cannot optimize the instructions for spilling the virtual registers either, as the mapping of virtual registers to physical registers greatly restrict the ability of late instruction schedulers to move instructions within the code of a program.